package simple

// https://leetcode-cn.com/problems/count-primes/
// 计算质数
// 基本算法: 直接通过n^2 查看这个数是否能被其他整数整除，时间复杂度O(n^2)
// 更优化的算法: 首先 比如24 = 12 * 2，12 本身已经能够推断出不是质数了，因此24 其实是不用单独判断的
// 或者换种说法，4*4 也不需要判断，已经可以通过比它更小的质数2 来算出来
// 最后的时间复杂度就是算2 的质数的时候复杂度最高，O(n * log2(n) )
func CountPrimes(n int) int {
	isPrimeArr := make([]bool, n+1)
	for index := 2; index <= n; index++ {
		isPrimeArr[index] = true
	}

	for i := 2; i*i <= n; i++ {
		if !isPrimeArr[i] {
			continue
		}
		for j := i * i; j <= n; j += i {
			isPrimeArr[j] = false
		}
	}

	primeCount := 0
	for index := 0; index < n; index++ {
		if isPrimeArr[index] {
			primeCount++
		}
	}
	return primeCount
}
